//判断字符串是否由其重复的子串构成 力扣459
//KMP算法 前缀表 
class Solution {
public:
	void getnext(int* next,string s)
	{
		int j = 0;
		next[0] = 0;
		for(int i = 1; i < s.size(); i++)
		{
			while(j > 0 && s[i] != s[j]) j = next[j-1];
			if(s[i] == s[j]) j++;
			next[i] = j;
		}
	}
	
	bool repeatedSubstringPattern(string s) {
		int len = s.size();
		int next[len];
		getnext(next,s);
		if(next[len-1] != 0 && len%(len-next[len-1])==0) return true;
		return false;
	}
};
